package logic;

//import gui.GraphGUI;

public class TwoOpt {

	public static Tour twoOpt(Graph g, Tour tour){
		int flip = 0;
		for(int l=0;l<7;l++){
			for(int i=0;i<g.vertices.length;i++){
//				Vertex t1 = tour.getCity(i);
				Vertex t1 = g.vertices[i];
				Vertex t2 = tour.next(t1);
				Vertex t4 = null;
				Vertex t3 = null;
				for(Vertex n : t1.topk){
					t3 = n;
					t4 = tour.prev(t3);
					int u1 = g.distMatrix[t3.index][t4.index];
					int v1 = g.distMatrix[t1.index][t2.index];
					int u2 = g.distMatrix[t1.index][t4.index];
					int v2 = g.distMatrix[t3.index][t2.index];
					if(t2 != n && ( u1 + v1 > u2 + v2 )){
						if(t2 == t4 ){
							t3=null;
							continue;
						}
						break;
					} else {
						t3 = null;
					}
				}
				if(t3!=null ){
					flip++;
					tour.flip(t1,t2,t3,t4);
				}
			}
		}
		if(TSPSolver.DEBUG){
			System.err.println("Completed with "+flip+" flips.");
		}
		return tour;
	}

}
